package dg;

import java.util.*;

public class FPTree {

    // 支持度阈值
    private final static int SUPPORT = 3;
    // 置信度阈值
    private final static double CONFIDENCE = 0.8;

    public static void main(String[] args) {
        ArrayList<String> itemCheckList = new ArrayList<>();
        itemCheckList.add("f;a;c;d;g;i;m;p");
        itemCheckList.add("a;b;c;f;l;m;o");
        itemCheckList.add("b;f;h;j;o");
        itemCheckList.add("b;c;k;s;p");
        itemCheckList.add("a;f;c;e;l;p;m;n");
        FPTree fpTree = new FPTree();
        fpTree.fpTree(itemCheckList);
    }

    /**
     * fp 树主程序
     *
     * @param itemCheckList
     */
    private void fpTree(ArrayList<String> itemCheckList) {
        List<NodeHead> nodeHeadList = new ArrayList<>();
        //保存所有的物品
        List<List<String>> dataList = new ArrayList<>();
        //存储频繁项
        Map<Integer, Integer> frequentMap = new HashMap<>();
        Map<String, Integer> itemIdMap = new HashMap<>();
        Map<Integer, String> idItemMap = new HashMap<>();
        getFirstFrequentSetMap(itemCheckList, nodeHeadList, dataList);
        //排序
        Collections.sort(nodeHeadList, new Comparator<NodeHead>() {
            @Override
            public int compare(NodeHead o1, NodeHead o2) {
                return o2.getCount() - o1.getCount();
            }
        });


        NodeHead temp = nodeHeadList.get(0);
        nodeHeadList.set(0, nodeHeadList.get(1));
        nodeHeadList.set(1, temp);

        createItemIdMap(itemIdMap, idItemMap, nodeHeadList);
        //做映射
        Map<String, Integer> itemFrequentIndexMap = nodeHeadListToMap(nodeHeadList);

        createFpTree(nodeHeadList, dataList, itemFrequentIndexMap);
        //深度优先遍历 FP 树
//        System.out.println();
//        System.out.println("==========================深度优先遍历 FP 树========================================");
//        System.out.println();
//        dpsFpTree(fpTree);
//        System.out.println();
//        System.out.println();
//        System.out.println();
/*        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(fpTree);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            queue.addAll(poll.getChildTreeNodes());
            System.out.println("当前节点 " + poll.getCurrentPoint() + "    数量  " + poll.getCount() + "    路径  "
                    + poll.getItemPathList() + "   点集  " + poll.getChildPointSet());

        }

        System.out.println("==============================================================================================");
        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println();*/



        getFrequentSet(nodeHeadList, itemIdMap, frequentMap);
        List<List<Integer>> countsList = createCountsList(frequentMap);
        int countsListSize = countsList.size();
        for (int i = 0; i < countsListSize - 1; i++) {
            for (int j = i + 1; j < countsListSize; j++) {
                createAssociationRule(countsList.get(i), countsList.get(j), frequentMap, idItemMap);
            }
        }
    }

    /**
     * 创建关联规则
     *
     * @param itemList
     * @param nextItemList
     * @param frequentMap
     */
    private void createAssociationRule(List<Integer> itemList, List<Integer> nextItemList, Map<Integer, Integer> frequentMap, Map<Integer, String> idItemMap) {
        if (nextItemList == null || nextItemList.isEmpty()) {
            return;
        }
        for (Integer item : itemList) {
            for (Integer nextItem : nextItemList) {
                Integer value = frequentMap.get(item);
                if ((nextItem & item) == item) {
                    Integer nextValue = frequentMap.get(nextItem);
                    float confidence = nextValue / (float) value;
                    if (value != null && nextValue != null && confidence >= CONFIDENCE) {
                        System.out.println(value + "   " + nextValue);
                        printAssociationRule(item, nextItem, confidence, idItemMap);
                    }
                }

            }
        }
    }

    /**
     * 打印关联规则
     *
     * @param item
     * @param nextItem
     * @param confidence
     * @param idItemMap
     */
    private void printAssociationRule(Integer item, Integer nextItem, float confidence, Map<Integer, String> idItemMap) {
        System.out.println(getItemStr(item, idItemMap) + " => " + getItemStr(nextItem, idItemMap) + " = " + confidence);
        System.out.println();
    }

    private List<List<Integer>> createCountsList(Map<Integer, Integer> frequentMap) {
        List<List<Integer>> countsList = new ArrayList<>();
        countsList.add(new ArrayList<>());
        Set<Integer> itemSet = frequentMap.keySet();
        List<Integer> itemList = new ArrayList<>(itemSet);
        for (Integer item : itemList) {
            int count = bitCount(item);
            if (countsList.size() < count) {
                addCounts(countsList, count);
            }
            countsList.get(count - 1).add(item);
        }
        return countsList;
    }

    private void addCounts(List<List<Integer>> countsList, int count) {
        int size = countsList.size();
        int temp = count - size;
        for (int i = 0; i < temp; i++) {
            countsList.add(new ArrayList<>());
        }
    }

    /**
     * 获取一个整数 二进制 1 的个数
     *
     * @param n
     * @return
     */
    private int bitCount(int n) {
        int c;
        for (c = 0; n != 0; ++c) {
            n &= (n - 1); // 清除最低位的1
        }
        return c;
    }


    /**
     * 获取整数的字符串表示形式
     *
     * @param item
     * @param idItemMap
     * @return
     */
    private String getItemStr(Integer item, Map<Integer, String> idItemMap) {
        int index = 1;
        StringBuilder sb = new StringBuilder();
        while (item != 0) {
            if ((item & 1) == 1) {
                sb.append(idItemMap.get(index));
            }
            item = item >> 1;
            index++;
        }
        return sb.toString();
    }

    /**
     * 创建 商品 和 id 之间的相互映射
     * id 代表商品的唯一标识  必须从 1 开始，后期便于计算
     *
     * @param itemIdMap
     * @param idItemMap
     * @param nodeHeadList
     */
    private void createItemIdMap(Map<String, Integer> itemIdMap, Map<Integer, String> idItemMap, List<NodeHead> nodeHeadList) {
        int index = 1;
        for (NodeHead nodeHead : nodeHeadList) {
            itemIdMap.put(nodeHead.getCurrentPoint(), index);
            idItemMap.put(index, nodeHead.getCurrentPoint());
            index++;
        }
    }

    /**
     * 获取频繁项集
     *
     * @param nodeHeadList
     * @param itemIdMap
     * @param frequentMap
     */
    private void getFrequentSet(List<NodeHead> nodeHeadList, Map<String, Integer> itemIdMap, Map<Integer, Integer> frequentMap) {
        List<List<String>> dataList;
        Map<String, Integer> itemFrequentIndexMap;
        for (NodeHead nodeHead : nodeHeadList) {
            dataList = new ArrayList<>();
            nodeHeadList = createFrequentSet(nodeHead, dataList);
            //排序
            Collections.sort(nodeHeadList, new Comparator<NodeHead>() {
                @Override
                public int compare(NodeHead o1, NodeHead o2) {
                    return o2.getCount() - o1.getCount();
                }
            });
            Map<Integer, Integer> currentFrequentMap = new HashMap<>();
            currentFrequentMap.put(createItemPathInteger(nodeHead.getCurrentPoint(), itemIdMap), nodeHead.getCount());
            itemFrequentIndexMap = nodeHeadListToMap(nodeHeadList);
            TreeNode fpTreeHead = createFpTree(nodeHeadList, dataList, itemFrequentIndexMap);
            dpsFpTree(fpTreeHead, currentFrequentMap, itemIdMap, nodeHead.getCurrentPoint());
            frequentMap.putAll(currentFrequentMap);
        }
    }

    /**
     * 获取经过路径的整数表示形式
     *
     * @param currentPoint
     * @param itemIdMap
     * @return
     */
    private Integer createItemPathInteger(String currentPoint, Map<String, Integer> itemIdMap) {
        List<String> currentPointList = new ArrayList<>();
        currentPointList.add(currentPoint);
        return createItemPathInteger(currentPointList, itemIdMap);
    }

    /**
     * 获取经过路径的整数表示形式
     *
     * @param itemPathList
     * @param itemIdMap
     * @return
     */
    private Integer createItemPathInteger(List<String> itemPathList, Map<String, Integer> itemIdMap) {
        int sum = 0;
        for (String itemPath : itemPathList) {
            Integer id = itemIdMap.get(itemPath);
            if (id != null) {
                sum = sum + (int) Math.pow(2, id - 1);
            }
        }
        return sum;
    }

    /**
     * 通过深度遍历获取模式基
     *
     * @param fpTree
     * @param frequentMap
     */
    private void dpsFpTree(TreeNode fpTree, Map<Integer, Integer> frequentMap, Map<String, Integer> itemIdMap, String currentPoint) {
        if (fpTree == null) {
            return;
        }
        Map<Integer, Integer> currentFrequentMap = new HashMap<>(frequentMap);
        List<TreeNode> childTreeNodes = fpTree.getChildTreeNodes();
        if (!childTreeNodes.isEmpty()) {
            for (TreeNode childTreeNode : childTreeNodes) {
                List<String> itemPathList = childTreeNode.getItemPathList();
                itemPathList.add(currentPoint);
                Integer itemPathInteger = createItemPathInteger(itemPathList, itemIdMap);
                Integer count = childTreeNode.getCount();
                Set<Integer> itemSet = currentFrequentMap.keySet();
                for (Integer item : itemSet) {
                    Integer currentItemPathInteger = createItemPathInteger(childTreeNode.getCurrentPoint(), itemIdMap);
                    if ((item & itemPathInteger) == item) {
                        int t = item | currentItemPathInteger;
                        frequentMap.put(t, count);
                    }
                }
                frequentMap.putAll(currentFrequentMap);
                dpsFpTree(childTreeNode, frequentMap, itemIdMap, currentPoint);
            }
        }
    }

    /**
     * 根据 FP 树生成频繁项集
     *
     * @param nodeHead
     * @param dataList
     * @return
     */
    private List<NodeHead> createFrequentSet(NodeHead nodeHead, List<List<String>> dataList) {
        List<NodeHead> nodeHeadList = new ArrayList<>();
        Map<String, Integer> itemMap = new HashMap<>();
        TreeNode currentTreeNode = nodeHead.getNext();
        while (currentTreeNode != null) {
            List<String> ItemPathList = currentTreeNode.getItemPathList();
            for (String itemPath : ItemPathList) {
                Integer count = itemMap.get(itemPath);
                if (count == null) {
                    itemMap.put(itemPath, currentTreeNode.getCount());
                } else {
                    itemMap.put(itemPath, count + currentTreeNode.getCount());
                }

            }
            int c = currentTreeNode.getCount();
            for (int i = 0; i < c; i++) {
                dataList.add(ItemPathList);
            }
            currentTreeNode = currentTreeNode.getNext();
        }
        Set<Map.Entry<String, Integer>> entries = itemMap.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getValue() >= SUPPORT) {
                nodeHeadList.add(new NodeHead(entry.getKey(), entry.getValue()));
            }
        }
        return nodeHeadList;
    }

    /**
     * 创建 FP 树
     *
     * @param nodeHeadList
     * @param dataList
     * @param itemFrequentIndexMap
     * @return
     */
    private TreeNode createFpTree(List<NodeHead> nodeHeadList, List<List<String>> dataList, Map<String, Integer> itemFrequentIndexMap) {
        //定义头点
        TreeNode treeNodeHead = new TreeNode();
        for (List<String> list : dataList) {
            TreeNode currentTreeNode = treeNodeHead;
            List<String> itemPath = new ArrayList<>();
            for (NodeHead nodeHead : nodeHeadList) {
                String currentPoint = nodeHead.getCurrentPoint();
                if (list.contains(currentPoint)) {
                    if (currentTreeNode.containsItem(currentPoint)) {
                        TreeNode treeNode = currentTreeNode.getTreeNode(currentPoint);
                        treeNode.addCount();
                        currentTreeNode = treeNode;
                        continue;
                    } else {
                        Integer index = itemFrequentIndexMap.get(currentPoint);
                        TreeNode treeNode = new TreeNode(currentPoint, 1);
                        currentTreeNode.addChildNode(treeNode);
                        treeNode.setItemPath(currentTreeNode);
                        itemPath.add(currentPoint);
                        currentTreeNode = treeNode;
                        NodeHead currentNodeHead = nodeHeadList.get(index);
                        currentNodeHead.addNextTreeNode(treeNode);
                    }
                }
            }
        }
        return treeNodeHead;
    }

    /**
     * 映射到 Map
     * 频繁项集 和 所在下标进行映射
     * key 频分项集   value  频繁项集所在的下标
     *
     * @param nodeHeadList
     * @return
     */
    private Map<String, Integer> nodeHeadListToMap(List<NodeHead> nodeHeadList) {
        Map<String, Integer> itemFrequentIndexMap = new HashMap<>();
        int size = nodeHeadList.size();
        for (int i = 0; i < size; i++) {
            NodeHead nodeHead = nodeHeadList.get(i);
            itemFrequentIndexMap.put(nodeHead.getCurrentPoint(), i);
        }
        return itemFrequentIndexMap;
    }


    /**
     * 获取频繁 1 项集
     *
     * @param itemCheckList
     * @param nodeHeadList
     * @param dataList
     */
    private void getFirstFrequentSetMap(ArrayList<String> itemCheckList, List<NodeHead> nodeHeadList, List<List<String>> dataList) {
        Map<String, Integer> itemMap = new HashMap<>();
        for (String itemCheck : itemCheckList) {
            Set<String> itemSet = new HashSet<>();
            String[] itemList = itemCheck.split(";");
            for (String item : itemList) {
                if (!itemSet.contains(item)) {
                    Integer count = itemMap.get(item);
                    if (count == null) {
                        itemMap.put(item, 1);
                    } else {
                        itemMap.put(item, ++count);
                    }
                    itemSet.add(item);
                }
            }
            dataList.add(new ArrayList<>(itemSet));
        }

        Set<Map.Entry<String, Integer>> entries = itemMap.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getValue() >= SUPPORT) {
                nodeHeadList.add(new NodeHead(entry.getKey(), entry.getValue()));
            }
        }
    }


}

/**
 * FP树节点
 */
class TreeNode {
    //当前节点 所有孩子节点的点集
    private List<String> childPointSet = new ArrayList<>();
    private List<String> itemPathList = new ArrayList<>();
    //计数 计算经过该点路径的数量
    private Integer count;
    //当前点的名称
    private String currentPoint;
    //孩子节点
    List<TreeNode> childTreeNodes = new ArrayList<>();
    private TreeNode next = null;

    public TreeNode() {
    }

    public TreeNode(String currentPoint, Integer count) {
        this.currentPoint = currentPoint;
        this.count = count;
    }

    public String getCurrentPoint() {
        return currentPoint;
    }

    public List<TreeNode> getChildTreeNodes() {
        return childTreeNodes;
    }

    public Integer getCount() {
        return count;
    }

    public List<String> getChildPointSet() {
        return childPointSet;
    }

    public List<String> getItemPathList() {
        return itemPathList;
    }

    public TreeNode getNext() {
        return next;
    }

    public void setNext(TreeNode next) {
        this.next = next;
    }

    /**
     * 判断在孩子节点中是否包含该节点
     *
     * @param currentPoint
     * @return
     */
    public boolean containsItem(String currentPoint) {
        if (childPointSet.contains(currentPoint)) {
            return true;
        }
        return false;
    }

    /**
     * 计数
     */
    public void addCount() {
        this.count++;
    }

    /**
     * 添加孩子节点
     *
     * @param currentPoint
     */
    public void addChildNode(TreeNode currentPoint) {
        this.childPointSet.add(currentPoint.currentPoint);
        this.childTreeNodes.add(currentPoint);
    }

    /**
     * 设置经过的路径
     *
     * @param currentTreeNode
     */
    public void setItemPath(TreeNode currentTreeNode) {
        this.itemPathList.addAll(currentTreeNode.itemPathList);
        if (currentTreeNode.currentPoint != null && !currentTreeNode.currentPoint.trim().isEmpty()) {
            this.itemPathList.add(currentTreeNode.currentPoint);
        }
    }

    /**
     * 根据当前节点的值,获取FP节点
     *
     * @param currentPoint
     * @return
     */
    public TreeNode getTreeNode(String currentPoint) {
        for (TreeNode childTreeNode : this.childTreeNodes) {
            if (childTreeNode.currentPoint.equalsIgnoreCase(currentPoint)) {
                return childTreeNode;
            }
        }
        return null;
    }
}

/**
 * 项头节点
 */
class NodeHead {
    //当前点的名称
    private String currentPoint;
    private Integer count;
    private TreeNode next = null;

    public NodeHead(String currentPoint, Integer count) {
        this.currentPoint = currentPoint;
        this.count = count;
    }

    public Integer getCount() {
        return count;
    }

    public String getCurrentPoint() {
        return currentPoint;
    }

    public TreeNode getNext() {
        return next;
    }

    public void addNextTreeNode(TreeNode treeNode) {
        if (this.next == null) {
            this.next = treeNode;
            return;
        }

        TreeNode currentTreeNode = this.next;
        while (currentTreeNode.getNext() != null) {
            currentTreeNode = currentTreeNode.getNext();
        }
        currentTreeNode.setNext(treeNode);
    }

}
